package com.cqs.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.*;

/**
 * Created by cqs on 2018/3/24.
 */
public class SearchA2DMatrix {

    public boolean searchMatrix2(int[][] matrix, int target) {

        ExecutorService exec = Executors.newFixedThreadPool(4);
        List<Callable<Boolean>> tasks = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            int[] arr = matrix[i];
            tasks.add(new Callable<Boolean>() {
                @Override
                public Boolean call() throws Exception {
                    return exists(arr, target);
                }
            });
        }
        try {
            List<Future<Boolean>> futures = exec.invokeAll(tasks);
            for (Future<Boolean> future : futures) {
                if (future.get()) {
                    return true;
                }
            }

        } catch (InterruptedException e) {

        } catch (ExecutionException e) {
            e.printStackTrace();
        } finally {
            exec.shutdown();
        }
        return false;
    }

    public boolean searchMatrix0(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            int[] arr = matrix[i];
            if (exists(arr, target)) return true;
        }
        return false;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int up = 0, down = matrix.length - 1;
        int mid = 0;
        while (up < down) {
            mid = (up + down) / 2;
            if (matrix[mid][0] == target) return true;
            if (matrix[mid][0] < target) {
                int[] arr = matrix[mid];
                if (matrix[mid][arr.length - 1] == target) return true;
                else if (matrix[mid][arr.length - 1] < target) up = mid + 1;
                else up = down = mid;
            } else {
                down = mid - 1;
            }
        }
        if (up == down) {
            return Arrays.binarySearch(matrix[up], target) >= 0;
        }
        return false;
    }


    private boolean exists(int[] array, int target) {
        return Arrays.binarySearch(array, target) >= 0;
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {3},
//                {1, 3, 5, 7},
//                {10, 11, 16, 20},
//                {23, 30, 34, 50}
        };
        int target = 3;
        SearchA2DMatrix s = new SearchA2DMatrix();
        System.out.println(s.searchMatrix(matrix, target));
        System.out.println(s.searchMatrix(matrix, 8));
        System.out.println(s.searchMatrix(matrix, 7));
        System.out.println(s.searchMatrix(matrix, 50));
        System.out.println(s.searchMatrix(matrix, 0));
    }

}
